<?php
/**
 * 冒泡排序
 * 思路分析：在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，
 * 让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
 */

$array = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39];

function bubbleSort($arr)
{
    $len = count($arr);
    //该层循环控制 需要冒泡的轮数
    for ($i = 0; $i < $len - 1; $i++) {
        //该层循环用来控制每轮 冒出一个数 需要比较的次数
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $max = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $max;
            }
        }
    }
    return $arr;
}


//print_r(bubbleSort($array));



/**
 * 优化冒泡算法
 * 如果第一步排序好了,上面的冒泡排序依旧会执行9遍的代码中，每一遍都能在(n-1)的数据比较，如果数组的长度n极大，这个消耗还是很严重的。
 * 所以我们首先要解决一下这个问题，怎么才能不造成无谓的数据比较的资源浪费。
 *
 * 优化策略:在程序中添加标识，用于记录每次外循环过程中，是否发生了数据的交换。
 * 如果没有发生数据的交换，就意味者在上一轮的外循环过程中，数据已经排序完成，
 * 不需要继续循环比较数据了，我们直接break掉就可以了。如果还存在这数据的交换，
 * 就意味着在之前的外部循环中，数据还没有排序好，这一轮排序操作或者接下来的排序操作才可以完成排序工作，
 * 我们还需要进行下一轮的排序来完成排序。
 */

function bubbleSortOptimization($rand_arr)
{
    $arr_count = count($rand_arr);
    for($i=0;$i<$arr_count;$i++){
        //设置flag变量，用来记录数据是否交换完成
        $flag = true;
        for($j=0;$j<$arr_count-1;$j++){
            if($rand_arr[$j] > $rand_arr[$j+1]){
                //进行交换
                $temp = $rand_arr[$j];
                $rand_arr[$j] = $rand_arr[$j+1];
                $rand_arr[$j+1] = $temp;
                $flag = false;
            }
        }
        if($flag){
            break;
        }
    }
    return $rand_arr;
}

//print_r(bubbleSortOptimization($array));

/**
 * 进一步优化
 * 说完上面的问题，咱们再来看下面的问题。当冒泡排序的外部循环每执行一次，
 * 就会将最大值(最小值)交换到数组的最前端或者数组的最后端，直接看下面的例子。

 * 经过第一轮排序以后会得到以下的结果:[ 4 , 6 , 2 , 7 , 8 , 0, 9 ] —-也就是说，
 * 我们再第一轮求出的最大值9，并且将这个值交换到数组的左部第一的位置上

 * 经过第二轮排序以后会得到以下的结果:[ 4 , 6 , 2 , 7 , 0 , 8 , 9 ] —-也就是说，
 * 我们再第二轮求出的次最大值8，并且将这个值交换到数组的左部第二的位置上

 * ……..

 * 依此类推，我们可以发现，每一轮循环完毕，都能求出某个位置上的应有的数据，并且完成交换。
 * 那么也就是说数组的左部(右部)逐渐变得有序，且有序部分的长度等于外部循环进行的轮数。
 * 既然数组的左部(右部)逐渐变得有序，那么每次循环过程中，
 * 我们就不需要再比较数组的左部(右部)的有序的部分了。

 * 优化策略:新增一个变量来记录某次外部循环过程中最后发生的数据交换的位置。
 * 使用上面记录的位置来作为下一次外部循环中的内部循环的终止条件，这样就能减少不必要数据比较过程。

 */
function bubbleSortNextOptimization($rand_arr)
{
    $arr_count = count($rand_arr);
    $last_pos = $arr_count; //记录每一次外部循环过程中，最后进行数据交换的位置
    $next_pos = $arr_count; //记录每一次数据交换的位置
    for($i=0;$i<$arr_count;$i++){
        for($j=0;$j<$last_pos-1;$j++){
            if($rand_arr[$j] > $rand_arr[$j+1]){
                //进行交换
                $temp = $rand_arr[$j];
                $rand_arr[$j] = $rand_arr[$j+1];
                $rand_arr[$j+1] = $temp;
                $next_pos = $j+1;
            }
        }
        //如果该轮循环得到的最后的数据交换位置等于上一轮循环得到的数据交换的位置，就意味着数组全部有序了
        if($last_pos == $next_pos){
            break;
        }else{//如果没有全部有序，就将last_pos设置为next_pos
            $last_pos = $next_pos;
        }
    }
    return $rand_arr;
}

//print_r(bubbleSortNextOptimization($array));


/**
 * 双向排序
 * 解决了上面的问题，我们还能不能进一步的提高冒泡算法的排序速度嘛？
 * 答案是可以的。我们可以采用双向排序的方式，进一步加快排序的速度。看下面的实现的例子:
 * 数组: [ 4 , 3 , 6 , 5 , 9 , 0 , 1 , 7 ]
 * 双向排序之正向排序(从左到右排序)：[ 3 , 4 , 5 , 6 , 0 , 1 , 7 , 9]
 * —计算出数组的最大值9，并将元素移动到数组的最右边
 * 双向排序之逆向排序(从右到左排序)：[ 0 , 3 , 4 , 5 , 6 , 1 , 7 , 9]
 * —计算出数组的最小值0，并将元素移动到数组的最左边
 * 第一次循环过程，计算出最大值并将该值移动到数组最右边，计算出最小值并将该值移动到数组的最左边。
 * 第二次循环过程中，计算出第二大的值并将数据移动到数组右边第二个的位置，
 * 计算出第二小的值并将数据移动到数组左边第二个的位置。也会说在一次双向排序循环过程中，
 * 求出数组左边以及数组右边各个位置响应的元素，并且移动到响应的位置。

 */


function bubbleSortBidirectionalSorting($rand_arr)
{
    $arr_count = count($rand_arr);
    $last_pos = $arr_count; //记录每一次外部循环过程中，最后进行数据交换的位置
    $next_pos = $arr_count; //记录每一次数据交换的位置
    for($i=0;$i<$arr_count;$i++){
        for($j=0;$j<$last_pos-1;$j++){
            if($rand_arr[$j] > $rand_arr[$j+1]){
                //进行交换
                $temp = $rand_arr[$j];
                $rand_arr[$j] = $rand_arr[$j+1];
                $rand_arr[$j+1] = $temp;
                $next_pos = $j+1;
            }
        }
        //如果该轮循环得到的最后的数据交换位置等于上一轮循环得到的数据交换的位置，就意味着数组全部有序了
        if($last_pos == $next_pos){
            break;
        }else{//如果没有全部有序，就将last_pos设置为next_pos
            $last_pos = $next_pos;
        }
    }
    return $rand_arr;
}

print_r(bubbleSortBidirectionalSorting($array));

/**
 * 结论
对这几种排序做了对比，用了1000个随机数组
没有进行优化，冒泡执行的时间38.826741201211
第一次优化后，冒泡执行的时间36.326452970505
第二次优化后，冒泡执行的时间24.916656017303
第三次优化后，冒泡执行的时间20.908751010895
 */
